package it.storm.solution;

/**
 * 1014. 最佳观光组合
 * https://leetcode-cn.com/problems/best-sightseeing-pair/
 */
public class Solutions_1014 {
    public static void main(String[] args) {
        int[] A = {8, 1, 5, 2, 6};  // output: 11   (8 + 5 + 0 - 2 = 11)
        int result = maxScoreSightseeingPair(A);
        System.out.println(result);
    }

    /**
     * 解法一：贪心算法（4ms）
     */
    public static int maxScoreSightseeingPair(int[] A) {
        // 默认设置左侧的最佳景点是索引 0 上的景点
//        int left = A[0] - 0;
        int left = A[0];
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < A.length; i++) {
            // 将第 i 个景点与 [0, i - 1] 区间中的最佳景点进行评分计算，比较并保存最高评分
            res = Math.max(res, A[i] + left - i);
            // left 始终是 [0, i] 中的最高得分景点
            // 如果 A[0] + 0 > A[1] + 1，那么 left 就是 A[0] - 0，否则就是 A[1] + 1
            left = Math.max(left, A[i] + i);
        }
        return res;
    }

    /**
     * 枚举（超时）
     */
    public static int maxScoreSightseeingPair2(int[] A) {
        int res = 0, cur = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                cur = A[i] + A[j] + i - j;
                res = Math.max(res, cur);
            }
        }
        return res;
    }
}
